package gramatica;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

import simbolo.NoTerminal;
import simbolo.Simbolo;
import simbolo.Terminal;

public class Gramatica {

	// Terminales
	private ArrayList<Terminal> terminales;
	// No Terminales
	private ArrayList<NoTerminal> noTerminales;
	// Simbolo inicial
	private NoTerminal simboloInicial; 
	// Producciones
	private Map<NoTerminal, Set<ParteDerecha>> producciones;
	
	public Gramatica() {
		terminales = new ArrayList<Terminal>();
		noTerminales = new ArrayList<NoTerminal>();
		producciones = new TreeMap<NoTerminal, Set<ParteDerecha>>();
	}
	
	public void iniciarProducciones() {
		// Defino vacíos los conjuntos de los no terminales en
		// las producciones. Después se agregarán a este conjunto
		// partes derechas que recojo de la gramática.
		for (NoTerminal nt : noTerminales) {
			producciones.put(nt, new TreeSet<ParteDerecha>());
		}
	}
	
	public void definirProduccion(NoTerminal noTerminal, ParteDerecha produccion) {
		Set<ParteDerecha> partesDerechas = producciones.get(noTerminal);
		partesDerechas.add(produccion);
	}
	
	public ArrayList<NoTerminal> getNoTerminales() {
		return noTerminales;
	}
	public void setNoTerminales(ArrayList<NoTerminal> noTerminales) {
		this.noTerminales = noTerminales;
	}
	public Map<NoTerminal, Set<ParteDerecha>> getProducciones() {
		return producciones;
	}
	public void setProducciones(Map<NoTerminal, Set<ParteDerecha>> producciones) {
		this.producciones = producciones;
	}
	public NoTerminal getSimboloInicial() {
		return simboloInicial;
	}
	public void setSimboloInicial(NoTerminal simboloInicial) {
		this.simboloInicial = simboloInicial;
	}
	public ArrayList<Terminal> getTerminales() {
		return terminales;
	}
	public void setTerminales(ArrayList<Terminal> terminales) {
		this.terminales = terminales;
	}
	
	public String toString() {
		String resultado = new String();
		
		resultado += "Terminales: " + terminales.toString() + "\n";
		resultado += "No terminales: " + noTerminales.toString() + "\n";
		resultado += "Símbolo inicial: " + simboloInicial.toString() + "\n";
		resultado += "Producciones:\n";
		for(NoTerminal nt : producciones.keySet()) {
			resultado += "\t" + nt.toString() + "->\n";
			for(ParteDerecha pd : producciones.get(nt)) {
				resultado += "\t\t" + pd.toString() + "\n";
			}
		}
		
		return resultado;
	}
	
	// Chequeo de gramática;
	public boolean isPropia() {
		return (isSinCiclos() && isSinInutiles() && isNoProduccionesLambda());
	}
	
	public boolean isApta() {
		//		 Veo que la gramática no tenga producciones lambda:
        boolean resultado = isNoProduccionesLambda();
        
        System.out.println("No tiene producciones lambda: " + resultado);
        if (resultado) {
        	resultado = isSinCiclos();
        	System.out.println("No tiene ciclos: " + resultado);
        }
        
        // Veo que la gramática sea unívocamente inversible:
        if (resultado) {
        	resultado = isUnivocamenteInversible();
        	System.out.println("Es unívocamente inversible: " + resultado);
        }
        
        if (resultado) {
        	resultado = isSinInutiles();
        	System.out.println("No tiene simbolos inútiles: " + resultado + "\n\n");
        }
        
        return resultado;
	}

	public boolean isSinCiclos() {
//		Asumiendo que no hay reglas borradoras
//		    - Comprobar que las partes derechas tienen más de un caracter.
//		    - Si alguna producción es de un caracter, seguirla hasta que
//		        - Derive en una cadena de más de un caracter, o
//		        - Derive en un terminal.
//		        - Si me encuentro con un no terminal igual al que venía rastreando, afirmo que la gramática tiene ciclos.
		boolean resultado = true;
		Iterator itNoTerminales = noTerminales.iterator();
		while (resultado && itNoTerminales.hasNext()){
			NoTerminal noTerminal = (NoTerminal) itNoTerminales.next(); 
			Iterator itPartesDerechas = producciones.get(noTerminal).iterator();
			while (resultado && itPartesDerechas.hasNext()) {
				ParteDerecha parteDerecha = (ParteDerecha) itPartesDerechas.next();
				if (parteDerecha.getSimbolos().size() == 1) {
					if (parteDerecha.getSimbolos().get(0) instanceof NoTerminal) {
						Set<NoTerminal> visitados = new TreeSet<NoTerminal>();
						visitados.add(noTerminal);
						resultado = explorarCiclosProduccion(visitados, (NoTerminal) parteDerecha.getSimbolos().get(0));
					}
				}
			}
		}
		return resultado;
	}

	private boolean explorarCiclosProduccion(Set<NoTerminal> visitados, NoTerminal noTerminal) {
		boolean resultado = true;
		Set<ParteDerecha> partesDerechas = producciones.get(noTerminal);
		Iterator itPartesDerechas = partesDerechas.iterator();
		while (resultado && itPartesDerechas.hasNext()) {
			ParteDerecha parteDerecha = (ParteDerecha) itPartesDerechas.next();
			if (parteDerecha.getSimbolos().size() == 1) {
				Simbolo s = parteDerecha.getSimbolos().get(0); 
				if (s instanceof NoTerminal) {
					if (visitados.contains((NoTerminal) s)) {
						resultado = false;
					}
					else {
						visitados.add((NoTerminal) s);
						resultado = explorarCiclosProduccion(visitados, (NoTerminal) s);
					}
				}
			}
		}
		
		return resultado;
	}

	public boolean isSinInutiles() {
		boolean resultado = true;
		
		Set<Simbolo> utiles = new TreeSet<Simbolo>();
		utiles.add(simboloInicial);
		Set<Simbolo> utilesAnteriores = new TreeSet<Simbolo>();
		
		while(!utiles.equals(utilesAnteriores)) {
			utilesAnteriores.clear();
			utilesAnteriores.addAll(utiles);
			for(Simbolo s : utilesAnteriores) {
				if (s instanceof NoTerminal) {
					Set<ParteDerecha> partesDerechas = producciones.get((NoTerminal) s);
					for (ParteDerecha parteDerecha : partesDerechas) {
						utiles.addAll(parteDerecha.getSimbolos());
					}
				}
			}
		}

		resultado = !(utiles.addAll(terminales));
		if (resultado) {
			resultado = !(utiles.addAll(noTerminales));
		}
		
		return resultado;
	}

	public boolean isNoProduccionesLambda() {
		boolean resultado = true;
		Iterator itSetsPartesDerechas = producciones.values().iterator();
		while (itSetsPartesDerechas.hasNext() && resultado) {
			Iterator itPartesDerecha = ((Set<ParteDerecha>) itSetsPartesDerechas.next()).iterator();
			while (itPartesDerecha.hasNext() && resultado) {
				resultado = !(((ParteDerecha) itPartesDerecha.next()).getSimbolos().isEmpty());
			}
		}
		
		return resultado;
	}
	
	public boolean isUnivocamenteInversible() {
		boolean resultado = true;
		
		Set<ParteDerecha> bolsa = new TreeSet<ParteDerecha>();
		Collection<Set<ParteDerecha>> gruposPartesDerechas = producciones.values();
		Iterator itConjPartesDerechas = gruposPartesDerechas.iterator();
 
		while (resultado && itConjPartesDerechas.hasNext()) {
			Set partesDerechas = (Set) (itConjPartesDerechas.next());
			Iterator itPartesDerechas = partesDerechas.iterator();
			while (resultado && itPartesDerechas.hasNext()) {
				resultado = bolsa.add((ParteDerecha) itPartesDerechas.next());
			}
		}
	
		return resultado;
	}
}
